package countSort;

public class CountBookSort {

    public static int[] countSort(int[] array){
        //得到数组中的最大最小值 计算差值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] >= max) max = array[i];
            if (array[i] <= min) min = array[i];
        }
        int different = max - min;
        //创建统计数组 并计算对应元素的个数
        int[] countArray = new int[different + 1];
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - min] ++;
        }
        //统计数组变形 后面的元素等于前面元素之和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
        //倒叙遍历原数组 从统计数组中找到正确的位置 输出到结果数组中
        int[] sortArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            sortArray[countArray[array[i] - min] - 1] = array[i];
            countArray[array[i] - min] --;
        }
        return sortArray;
    }
}
